//https://leetcode.cn/problems/maximum-profit-in-job-scheduling/description/?envType=daily-question&envId=2024-05-04


class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<pair<int, pair<int, int>>> mp;
        for(int i=0;i<n;i++){
            mp.emplace_back(pair(endTime[i], pair(startTime[i], profit[i])));
        }
        sort(mp.begin(), mp.end());

        vector<int> dp(n, 0);
        dp[0] = mp[0].second.second;
        for(int i=1;i<n;i++){
            int current_pro = mp[i].second.second;
            int pos = mp[i].second.first;
            int prev = -1;
            for(int j = i-1;j>=0;j--){
                if(mp[j].first<=pos){
                    prev = j;
                    break;
                }
            }
            if(prev!=-1){
                current_pro +=dp[prev];
            }
            dp[i] = max(dp[i-1], current_pro);
        }
        return dp[n-1];
    }
};